package com.lfg.leetcode.leetcode500;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串
 */
public class No516longestPalindromeSubseq {

    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab"));
    }


    public static int longestPalindromeSubseq(String s) {
        int length = s.length();
        int[][] dp = new int[length][length];
        for (int j = 0; j < length; j++) {
            dp[j][j] = 1;
            for (int i = j - 1; i >= 0; i--) {
                if (s.charAt(j) == s.charAt(i)) {
                    if (j == i + 1) {
                        dp[i][j] = 2;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][dp.length - 1];
    }
}
